"Gonna Get Over You" được chắp bút bởi chính Bareilles và Sam Farrar, người chơi guitar bass trong nhóm nhạc rock Phantom Planet.[3] Bareilles thu âm một phiên bản mới cùng nam nghệ sĩ Ryan Tedder từ nhóm nhạc OneRepublic. Phiên bản mới này được phát hành dưới dạng đĩa đơn vào ngày 20 tháng 9 năm 2011 trên iTunes.[3]

Bài hát này nhận được nhiều đánh giá tích cực từ phía chuyên môn. Jon Pareles viết trên The New York Times rằng "bài hát ballad hậu chia tay" này chính là "sự biến đổi tân thời của dòng nhạc doo-wop"[2] Jim Farber từ New York Daily News cho rằng bài hát "mang nhịp điệu hành khúc, khiến một bài hát buồn lại mang một không khí vui tuơi đến thế."[4] Will Hermes từ Rolling Stone xem đây như là một trong những bài hát xuất sắc nhất trong album, khi viết rằng đây là "một bài hát doo-wop pop khôi hài và quyến rũ."[1] Allison Stewart từ Washington Post gọi nó là một "bài hát pop vui nhộn và ngập tràn hòa âm."[5][6][7]